
package com.liwt.liqian;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * 证据理论中有关集合与排列组合操作相关
 * 
 * @author likebamboo
 */
public class DSEvidential {
    /**
     * 求两个 Integer 集合的交集 交集
     * 
     * @param a
     * @param b
     * @return
     */
    public static ArrayList<Integer> intersection(ArrayList<Integer> a, ArrayList<Integer> b) {
        if (a == null || b == null) {
            return null;
        }
        ArrayList<Integer> result = new ArrayList<Integer>();
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < b.size(); j++) {
                if (a.get(i) == b.get(j)) {
                    result.add(a.get(i));
                }
                if (a.get(i) < b.get(j)) {
                    break;
                }
            }
        }
        return result;
    }

    /**
     * 将特定格式 （如 [1,2,3,5,6]）的字符串转为ArrayList
     * 
     * @param str
     * @return
     */
    public static ArrayList<Integer> str2List(String str) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        str = str.replace("[", "").replace("]", "");
        if (!str.contains(",")) {
            try {
                int one = Integer.parseInt(str);
                result.add(one);
            } catch (Exception e) {
                e.printStackTrace();
            }
            return result;
        }
        String[] split = str.split(",");
        for (String item : split) {
            result.add(Integer.parseInt(item));
        }
        return result;
    }

    /**
     * 求 C(n,r)的所有组合数 （即 求从1..n 中 取 r个元素的所有取法）
     * 
     * @param n
     * @param r
     * @return
     */
    private static ArrayList<String> arrange(int n, int r) {
        int i = 0, j;
        String s, prefix = "";
        int[] a = new int[n];
        ArrayList<String> result = new ArrayList<String>();
        a[i] = 1;
        while (true) {
            if ((a[i] - i) <= (n - r + 1)) {
                if (i == (r - 1)) {
                    s = "";
                    for (j = 0; j < r; j++) {
                        s += prefix + a[j];
                        prefix = ",";
                    }
                    result.add(s);
                    a[i] = a[i] + 1;
                    prefix = "";
                    continue;
                }
                i = i + 1;
                a[i] = a[i - 1] + 1;
            } else {
                if (i == 0) {
                    break;
                }
                i = i - 1;
                a[i] = a[i] + 1;
            }
        }
        return result;
    }

    /**
     * 求 1。。。n的所有组合
     * 
     * @param count
     * @return
     */
    public static ArrayList<String> getRow(int count) {
        ArrayList<String> result = new ArrayList<String>();
        for (int i = 1; i <= count; i++) {
            for (String item : arrange(count, i)) {
                result.add(item);
            }
        }

        return result;
    }

    /**
     * 对特定格式的字符串求交集
     * 
     * @param a a字符串。
     * @param b b字符串。
     * @return
     */
    public static String intersection(String a, String b) {
        String result = "", prefix = "";
        for (int i = 0; i < a.length(); i++) {
            for (int j = 0; j < b.length(); j++) {
                if (a.charAt(i) != ',' && a.charAt(i) == b.charAt(j)) {
                    result += prefix + a.charAt(i);
                    prefix = ",";
                    // 找到匹配的之后，后面的肯定不匹配，直接跳出第二重循环，继续外层循环
                    break;
                }
            }
        }
        return result;
    }

    public static void main(String args[]) {
        System.out.println("请输入一个小于10的整数");
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        while (count > 10) {
            System.out.println("你输入的值超过了10 ，请重新输入");
            count = in.nextInt();
        }
        in.close();
        for (int i = 1; i <= count; i++) {
            for (String item : arrange(count, i)) {
                System.out.println(item);
            }
        }
    }
}
